21
21

Apr 30, 2014
04/14

by
Microsoft Research

movies

######
eye 21

######
favorite 0

######
comment 0

An evolutionarily stable strategy (ESS) is an equilibrium strategy that is immune to invasions by rare alternative ('mutant') strategies. Unlike Nash equilibria, ESS do not always exist in finite games. In this paper, we address the question of what happens when the size of the game increases: does an ESS exist for 'almost every large' game? Letting the entries in the n x n game matrix be randomly chosen according to an underlying distribution F, we study the number of ESS with support of size...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Sergiu Hart

31
31

Sep 28, 2014
09/14

by
Microsoft Research

movies

######
eye 31

######
favorite 0

######
comment 0

We study random walks on the uniform spanning tree (UST) on Z 2 . We obtain estimates for the transition probabilities of the random walk, the distance of the walk from its starting point after n steps, and exit times of both Euclidean balls and balls in the intrinsic graph metric. In particular, we prove that the spectral dimension of the uniform spanning tree on Z 2 is 16/13 almost surely. In order to prove these results, we use the work of Barlow, Jarai, Kumagai, Misumi and Slade on random...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Robert Masson

39
39

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 39

######
favorite 0

######
comment 0

We provide a sufficient condition for the continuity of real valued permanental processes.When applied to the subclass of permanental processes which consists of squares of Gaussian processes, we obtain the sufficient condition for continuity which is also known to be necessary. Using an isomorphism theorem of Eisenbaum and Kaspi which relates Markov local times and permanental processes, we obtain a general sufficient condition for the joint continuity of the local times. We show that for...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Jay Rosen

16
16

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 16

######
favorite 0

######
comment 0

We will present the proof of a conjecture of B. Nienhuis on the number ofself-avoiding walks on the honeycomb lattice. More precisely, we will provethat the connective constant of the lattice equals the square root of (2+√2).This theorem is the first step towards a deeper understanding of self-avoiding walks. Wewill state some conjectures on the scaling-limit behavior of these walks. ©2010 Microsoft Corporation. All rights reserved.

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Hugo Duminil-Copin

19
19

Sep 30, 2014
09/14

by
Microsoft Research

movies

######
eye 19

######
favorite 0

######
comment 0

A well known conjecture asserts that on any graph the random walk and the interchange process have the same spectral gap.I will present recent work in collaboration with T.M. Liggett and T. Richthammer, in which we prove the conjecture using a recursive strategy. The main novelty is an idea based on electric network reduction, which allows us to reduce the problem to the proof of anew comparison inequality between certain weighted graphs. ©2010 Microsoft Corporation. All rights reserved.

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Pietro Caputo

24
24

Oct 5, 2014
10/14

by
Microsoft Research

movies

######
eye 24

######
favorite 0

######
comment 0

When agents have conflicting preferences over a set of alternatives and they want to make a joint decision, a natural way to do so is by voting. How to design and analyze desirable voting rules has been studied by economists for centuries. In recent decades, technological advances, especially those in the Internet economy, have introduced many new applications for voting theory. For example, we can rate movies based on people’s preferences, as done on many movie recommendation sites. However,...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Lirong Xia

18
18

Oct 5, 2014
10/14

by
Microsoft Research

movies

######
eye 18

######
favorite 0

######
comment 0

We close the problem of understanding the space complexity of pth moment estimation in data streams for 0 p = 2 by giving the first optimal upper and lower bounds. In this problem, a high-dimensional vector receives a long sequence of coordinate-wise updates, and we must output a low relative-error approximation of the pth moment at the end of the stream while keeping a memory footprint exponentially smaller than the vector length. This problem has applications in network traffic monitoring,...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Jelani Nelson

28
28

Oct 5, 2014
10/14

by
Microsoft Research

movies

######
eye 28

######
favorite 0

######
comment 0

In recent years, the emergence of massive computing tasks that arise in context of web applications and networks has made the need for efficient graph algorithms more pressing than ever. In particular, it lead us to focus on reducing the running time of the algorithms to make them as fast as possible, even if it comes at a cost of reducing the quality of the returned solution. This motivates us to expand our algorithmic toolkit to include techniques capable of addressing this new challenge. In...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Aleksander Madry

68
68

Feb 13, 2014
02/14

by
Microsoft Research

movies

######
eye 68

######
favorite 0

######
comment 0

The talk focuses on expander graphs in conjunction with the combined use of SDPs and eigenvalue techniques for approximating optimal solutions to combinatorial optimization problems. In the first part of the talk I will explain how to construct cost-effective, expanding networks by using 'local' sparsifiers of graphs that emerge as a solution to a semidefinite program. In the second part of the talk I will show that the Unique Games Conjecture is false when the underlying constraint graph is a...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Alexandra Kolla

49
49

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 49

######
favorite 0

######
comment 0

We study the following model for mobile wireless networks. At time 0, nodes are distributed as a Poisson point process with intensity λ over R 2 . We let nodes move independently in continuous time according to Brownian motion, and assume that at any time two nodes can exchange message iff their current distance is at most 1. In contrast with the case of static networks, where the network is usually required to be connected (and therefore limited to a finite region of R 2 ), in a mobile...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Alexandre Stauffer

50
50

Feb 17, 2014
02/14

by
Microsoft Research

movies

######
eye 50

######
favorite 0

######
comment 0

We discuss several fascinating concepts and algorithms in graph theory that arose in the design of a nearly-linear time algorithm for solving diagonally-dominant linear systems. We begin by defining a new notion of what it means to approximate a graph by another graph, and explain why these sparse approximations enable the fast solution of linear equations. To build these sparsifiers, we rely on low-stretch spanning trees, random matrix theory, spectral graph theory, and graph partitioning...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Dan Alan Spielman

22
22

Feb 17, 2014
02/14

by
Microsoft Research

movies

######
eye 22

######
favorite 0

######
comment 0

This is a two-part talk. In the first part, we prove a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only pairs of cards. In the second part, we use the theorem to obtain improved bounds for two previously studied models. Our first application is the following shuffle introduced by Thorp in 1973. Suppose the number of cards n is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Ben Morris

78
78

Oct 4, 2014
10/14

by
Microsoft Research

movies

######
eye 78

######
favorite 0

######
comment 0

Khot's Unique Games Conjecture (UGC) is one of the most central open problems in computational complexity theory. UGC asserts that for a certain constraint satisfaction problem, it is NP-hard to decide whether there is a labeling that satisfies almost all the constraints or, for every labeling, the fraction of the constraints satisfied is very small. Since its origin, the UGC has been applied with remarkable success to prove tight hardness of approximation results for several important NP-hard...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Alexandra Kolla

39
39

Oct 5, 2014
10/14

by
Microsoft Research

movies

######
eye 39

######
favorite 0

######
comment 0

Planar maps are embeddings of connected planar graphs in the plane considered up to continuous deformation. We will present a “master bijection” for planar maps and show that it can be specialized in various ways in order to count several families of maps. More precisely, for each integer d we obtain a bijection between the family of maps of girth d and a family of decorated plane trees. This gives new counting results for maps of girth d counted according to the degree distribution of...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Olivier Bernardi

45
45

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 45

######
favorite 0

######
comment 0

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices with edge weights chosen independently and uniformly at random from [0,1] is O(n 2 ) , in expectation and with high probability. This resolves a long standing open problem. Joint work with Y. Peres, D. Sotnikov and U. Zwick ©2010 Microsoft Corporation. All rights reserved.

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Benny Sudakov

27
27

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 27

######
favorite 0

######
comment 0

Nash equilibrium, integer factorization, and stable configuration of a Hopfield net are examples of total functions, problems in NP that are guaranteed to always have solutions. Each such problem is an implicit existence theorem; consequently, total functions are categorized by the elementary argument involved in the proof of the theorem: Pigeonhole principle, parity argument, conservation of degree, or potential function (no other kinds are known...). We will survey this area, and introduce a...

Topics: Microsoft Research, Microsoft Research Video Archive, Nikhil Devanur and Yuval Peres, Christos...

56
56

Dec 26, 2014
12/14

by
Microsoft Research

movies

######
eye 56

######
favorite 0

######
comment 0

I will briefly recall the connection between the Sparsest Cut problem in graphs and low-distortion embeddings of finite metric spaces into L 1 . Then I will talk about a recent approach to lower bounds pioneered by Cheeger and Kleiner (2006), following a conjecture we made with Naor (2003). The main idea is to develop a differentiation theory for L 1 -valued mappings. I will discuss a discrete version of this theory (following Eskin-Fisher-Whyte and Lee-Raghavendra). I will then construct a...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, James Lee

18
18

Sep 28, 2014
09/14

by
Microsoft Research

movies

######
eye 18

######
favorite 0

######
comment 0

Myerson has argued that the Nash equilibrium lies at the foundations of modern economic thought, and yet the dark computational side of the concept keeps getting gloomier. We show that playing games under considerations of risk, disambiguating games via equilibrium selection a`-la Harsanyi-Selten, and computing equilibria by the homotopy method, are all rife with very serious complexity impediments. Joint work with Paul Goldberg and Amos Fiat. ©2010 Microsoft Corporation. All rights reserved.

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Christos Papadimitriou

66
66

Apr 30, 2014
04/14

by
Microsoft Research

movies

######
eye 66

######
favorite 0

######
comment 0

Let C 1 denote the largest connected component of the critical Erdos-Renyi random graph G(n,1/n). We show that, typically, the diameter of C 1 is of order n 1/3 and the mixing time of the lazy simple random walk on C 1 is of order n. The latter answers a question of Benjamini, Kozma and Wormald. These results extend to clusters of size n 2/3 of p-bond percolation on any d-regular n-vertex graph where such clusters exist, provided that p(d-1) ≤ 1 + O(n -1/3 ). Joint work with Yuval Peres....

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Asaf Nachmias

27
27

Apr 30, 2014
04/14

by
Microsoft Research

movies

######
eye 27

######
favorite 0

######
comment 0

We study the k -core of a random (multi) graph on n vertices with a given degree sequence. We let n tend to infinity. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the k -core is empty, and other conditions that imply that with high probability the k -core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Malwina Luczak

19
19

Apr 30, 2014
04/14

by
Microsoft Research

movies

######
eye 19

######
favorite 0

######
comment 0

Consider a repeated two-person game. The question is how much smarter a player must be in order to effectively predict the moves of the other player. The answer depends on the formal definition of effective prediction, the number of actions each player has in the stage game, as well as on the measure of smartness. Effective prediction means that, no matter what the stage-game payoff function, the player can play (with high probability) a best reply in most stages. Neyman and Spencer [4] provide...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Abraham Neyman

42
42

Oct 2, 2014
10/14

by
Microsoft Research

movies

######
eye 42

######
favorite 0

######
comment 0

We consider network contribution games, where each agent in a social network has a budget of effort that it can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Elliot Anshelevich

28
28

Oct 6, 2014
10/14

by
Microsoft Research

movies

######
eye 28

######
favorite 0

######
comment 0

We consider the Max-Min Allocation problem, in which we are given a set of m agents and a set of n items, together with utilities u(A,i) of agent A for item i. Our goal is to allocate items to agents to maximize fairness. Specifically, the utility of an agent is the sum of its utilities for the items it receives, and we seek to maximize the minimum utility of any agent. While this problem has received much attention, its approximability has not been well-understood thus far: the best previously...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Julia Chuzhoy

65
65

Feb 13, 2014
02/14

by
Microsoft Research

movies

######
eye 65

######
favorite 0

######
comment 0

In this talk we will demonstrate iterative methods as a general technique to analyze linear programming formulations of combinatorial optimization problems. We first show an application of the method to the Minimum Bounded Degree Spanning Tree problem. We present a polynomial time algorithm that returns a spanning tree of optimal cost while exceeding the degree bound of any vertex by at most an additive one. This is the best possible result for this problem and settles a 15-year-old conjecture...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Mohit Singh

36
36

Feb 16, 2014
02/14

by
Microsoft Research

movies

######
eye 36

######
favorite 0

######
comment 0

Most combinatorial optimization problems of interest are NP-hard to solve exactly. To cope with this intractability, one settles for approximation algorithms with provable guarantee on the quality of approximation. Despite great success in designing approximation algorithms, underlying a vast majority of the work is the technique of linear programming, or more generally semi-definite programming. This poses the natural question: How far can we push the technique of semi-definite programming?...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Prasad Nagaraj Raghavendra

128
128

May 8, 2014
05/14

by
Microsoft Research

movies

######
eye 128

######
favorite 0

######
comment 0

Given a point process M of intensity one in the plane, the well-known Voronoi tesselation assigns a polygon (of different area) to each point of M. The geometry of 'fair' allocations (assigning unit area to each point of M) is richer and more mysterious: see http://www.math.ubc.ca/~holroyd/stable.html There is a unique 'fair' allocation that is 'stable' in the sense of the Gale-Shapley stable marriage problem, every point of M is assigned a bounded region with finitely many components, but...

Topics: Microsoft Research, Microsoft Research Video Archive, Scott Sheffield, Yuval Peres

20
20

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 20

######
favorite 0

######
comment 0

There is an increasing demand for the analysis of large amounts of data of many different kinds. Often the data isequipped with a notion of distance, reflecting notions of similarity of the data. Further, it is often the case that the notion of similarityis not backed up by theoretical constructions, but simply reflects an investigator's intuitive notion of similarity. This means thatin studying the data set, one should perform analyses which have some degree of robustness to small changes in...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Gunnar Carlsson

49
49

Oct 30, 2014
10/14

by
Microsoft Research

movies

######
eye 49

######
favorite 0

######
comment 0

Consider percolation on the Hamming cube 0,1 n at the critical probability p c (at which the expected cluster size is 2 n/3 ). It is known that if p=p c (1+O(2 -n/3 ), then the largest component is of size roughly 2 2n/3 with high probability and that this quantity is non-concentrated. We show that for any sequence eps(n) such that eps(n)2 -n/3 and eps(n)=o(1) percolation at p c (1+eps(n)) yields a largest cluster of size (2+o(1))eps(n)2 n . This result settles a conjecture of Borgs, Chayes,...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Asaf Nachmias

22
22

Feb 17, 2014
02/14

by
Microsoft Research

movies

######
eye 22

######
favorite 0

######
comment 0

This is a two-part talk. In the first part, we prove a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only pairs of cards. In the second part, we use the theorem to obtain improved bounds for two previously studied models. Our first application is the following shuffle introduced by Thorp in 1973. Suppose the number of cards n is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Ben Morris

51
51

Feb 10, 2014
02/14

by
Microsoft Research

movies

######
eye 51

######
favorite 0

######
comment 0

2:00 - 2:30 Olle Häggström (Chalmers) Percolation, mass transport and cluster indistinguishability 2:35 - 3:05 Yuval Peres (Microsoft) Connectivity Probability in Critical Percolation: An unpublished gem from Oded ©2009 Microsoft Corporation. All rights reserved.

Topics: Microsoft Research, Microsoft Research Video Archive, David Wilson, Yuval Peres, Prasad Tetali,...

41
41

Apr 30, 2014
04/14

by
Microsoft Research

movies

######
eye 41

######
favorite 0

######
comment 0

See http://www.math.ubc.ca/~holroyd/sort for pictures. Joint work with Omer Angel, Dan Romik and Balint Virag. Sorting a list of items is perhaps the most celebrated problem in mathematical computer science. If one must do this by swapping neighboring pairs, the worst initial condition is when the n items are in reverse order, in which case n choose 2 swaps are needed. A sorting network is any sequence of n choose 2 swaps which achieves this. We investigate the behavior of a uniformly random...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Alexander E. Holroyd

41
41

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 41

######
favorite 0

######
comment 0

We present an algorithm for the sparsest cut problem that simultaneously achieves the better approximation factor of SDP/multicommodity-flow based algorithms and the subquadratic running time of single-commodity flow based algorithms. The idea is that we can turn Arora, Rao, and Vazirani's matching-chaining argument into an algorithm for finding good augmenting paths in a multicommodity flow network. Our analysis follows ARV's, making essential use of measure concentration on the sphere. ©2010...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Jonah Sherman

25
25

Feb 10, 2014
02/14

by
Microsoft Research

movies

######
eye 25

######
favorite 0

######
comment 0

The multiple intents re-ranking problem was introduced recently by Azar, Gamzu and Xin (STOC 2009) in the context of ordering results of a web search query. In this problem, we are given a universe of elements U and a collection of subsets S1,S2,..,Sm. Additionally, each set S has a covering requirement of K(S). The goal is to order the elements in U to minimize average covering time of a set, where set S is said to be covered at time t, if t is the earliest time at which K(S) elements from S...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Nikhil Bansal

17
17

Feb 13, 2014
02/14

by
Microsoft Research

movies

######
eye 17

######
favorite 0

######
comment 0

Technology continues to move in the direction of parallel computation, whether it be in a computer or across the internet. Second order effects such as the communication needed to carry out a distributed algorithm have become a concern. In this light, we take an information theoretic look at the fundamental communication requirements in networks for distributing tasks. The model is simple: tasks are numbered; some nodes in the network are assigned tasks; others have to choose from the remaining...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Paul Cuff

149
149

Oct 6, 2014
10/14

by
Microsoft Research

movies

######
eye 149

######
favorite 0

######
comment 0

Sixty years ago, at the Institute for Advanced Study in Princeton, New Jersey, a 32 x 32 x 40-bit matrix of 24-microsecond random access memory was undergoing initial tests. John von Neumann (1903-1957) succeeded in jump-starting the digital revolution by bringing engineers into the den of the mathematicians, rather than by bringing mathematicians into a den of engineers. This implementation of Alan Turing’s Universal Machine broke the distinction between numbers that mean things and numbers...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, George Dyson

48
48

Dec 7, 2014
12/14

by
Microsoft Research

movies

######
eye 48

######
favorite 0

######
comment 0

There exists an entropy-preserving equivariant surjective map from the d-dimensional critical sandpile model to a certain closed, shift-invariant subgroup of the Cartesian product of infinitely many cycles, one for each node of the d-dimensional integer lattice (the 'harmonic model'). A similar map can be constructed for the dissipative abelian sandpile model and be used to prove uniqueness and the Bernoulli property of the measure of maximal entropy for that model. (Joint work with Evgeny...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Klaus Schmidt

25
25

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 25

######
favorite 0

######
comment 0

We will present Talagrand's majorizing measure theory, which gives tight estimates for maxima of Gaussian processes, including the full proof and an extension to a weak version of the Bernoulli conjecture. This is the second lecture in a series specifically designed to be accessible to beginners in the field. The format will be informal and questions will be encouraged Further lectures will be scheduled later to discuss more advanced aspects. ©2010 Microsoft Corporation. All rights reserved.

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, James Lee

34
34

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 34

######
favorite 0

######
comment 0

We will present Talagrand's majorizing measure theory, which gives tight estimates for maxima of Gaussian processes, including the full proof and an extension to a weak version of the Bernoulli conjecture. This is the third lecture in a series specifically designed to be accessible to beginners in the field. The format will be informal and questions will be encouraged ©2010 Microsoft Corporation. All rights reserved.

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, James Lee

15
15

Apr 30, 2014
04/14

by
Microsoft Research

movies

######
eye 15

######
favorite 0

######
comment 0

The dynamical system in the repeated play of a game is 'uncoupled' if each player initially knows only his own payoff function. We study the effects of this natural assumption on the possibility and impossibility of reaching Nash and correlated equilibria, and on the communication complexity that is involved. ©2007 Microsoft Corporation. All rights reserved.

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Sergiu Hart

11
11

Feb 13, 2014
02/14

by
Microsoft Research

movies

######
eye 11

######
favorite 0

######
comment 0

For Markov random fields temporal mixing, the time it takes for the Glauber dynamics to approach it's stationary distribution, is closely related to the spatial mixing properties of the measure such as uniqueness and the reconstruction problem. Such questions are of importance in probability, statistical physics and theoretical computer science. I will survey some recent progress in understanding the mixing time of the Glauber dynamics as well as related results on spatial mixing. ©2009...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Allan Sly

44
44

Oct 5, 2014
10/14

by
Microsoft Research

movies

######
eye 44

######
favorite 0

######
comment 0

We discuss a recent technique for dealing with k-independent families of random variables. The basic idea in showing that F is fooled by k-independence is to approximate by a smooth function F~ and note that the expectation of the Taylor polynomials are determined by k-independence. F~ can be obtained by convolving F with the Fourier transform of a compactly supported bump function. We discuss the development of this technique, leading up to the proof that limited independence fools degree 2...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Daniel Kane

53
53

Oct 6, 2014
10/14

by
Microsoft Research

movies

######
eye 53

######
favorite 0

######
comment 0

In this talk I shall sketch some results Oliver Riordan of Oxford and I have obtained on the critical probabilities in percolation. The story starts with Scullard and Zi, who recently pointed out that a broad class of planar percolation models are self-dual. They stated that in a variety of classes of models depending on a parameter, the parameter giving self-duality is the critical value for percolation. However, noticing self-duality is simply the starting point: the mathematical difficulty...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Bela Bollobas

62
62

Oct 30, 2014
10/14

by
Microsoft Research

movies

######
eye 62

######
favorite 0

######
comment 0

The Abelian sandpile growth model is a deterministic diffusion process for configurations of chips on the integer lattice. I will discuss joint work with Wesley Pegden on the scaling limit of the stable configurations. ©2011 Microsoft Corporation. All rights reserved.

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Charles Smart

8
8.0

Sep 30, 2014
09/14

by
Microsoft Research

movies

######
eye 8

######
favorite 0

######
comment 0

How can we efficiently aggregate rankings, cut a graph into two parts with many edges between them, pack items into bins, cluster items using pairwise similarity information, route vehicles in the Euclidean plane, or construct a Steiner tree in a planar graph? All these examples of optimization problems are NP-hard, yet, under some mild assumptions, they all have near-optimal solutions that can be computed in (high) polynomial time. I will present a few algorithmic techniques and their...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Claire Mathieu

89
89

Oct 6, 2014
10/14

by
Microsoft Research

movies

######
eye 89

######
favorite 0

######
comment 0

Talk 1: 3:30 to 4:15 Title: Probabilistic Approximation Theorems in Game Theory and Stochastic Optimization Speaker: Costis Daskalakis, MIT Abstract: In Economics, reliability theory and other domains, uncertainty is often modeled assuming Bayesian knowledge about unknown parameters. This assumption enables important results, e.g. Nash's theorem on the existence of equilibria in randomized strategies in games, and Myerson's theorem on revenue-optimal auctions. On the other hand, stochastic...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Costis Daskalakis and Jason...

34
34

Dec 6, 2014
12/14

by
Microsoft Research

movies

######
eye 34

######
favorite 0

######
comment 0

More than twenty years ago, Manickam, Miklos, and Singhi conjectured that for any integers n ≥ 4k , every set of n real numbers with nonnegative sum has at least binom n-1k-1 k -element subsets whose sum is also nonnegative. In this talk we discuss the connection of this problem with matchings and fractional covers of hypergraphs, and with the question of Feige and Samuels on estimating the probability that the sum of nonnegative independent random variables exceeds its expectation by a given...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Benny Sudakov

39
39

Sep 28, 2014
09/14

by
Microsoft Research

movies

######
eye 39

######
favorite 0

######
comment 0

By a classical theorem of Marstrand, if X is a set in the plane then almost every linear projection of X onto a line has the largest possible dimension, i.e. min1,dim(X). However, in general the dependence of this number on the projection is quite bad and is not well understood even in very simple examples. In joint work with Pablo Shmerkin we show that for a large class of fractals which arise from arithmetic, dynamical or combinatorial constructions there is some semi-continuity in the...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Michael Hochman

10
10.0

Dec 6, 2014
12/14

by
Microsoft Research

movies

######
eye 10

######
favorite 0

######
comment 0

The Gaussian central limit theorem says that for a wide class of stochastic systems, the bell curve (Gaussian distribution) describes the statistics for random fluctuations of important observables. In this talk I will look beyond this class of systems to a collection of probabilistic models which include random growth models, polymers,particle systems, matrices and stochastic PDEs, as well as certain asymptotic problems in combinatorics and representation theory. I will explain in what ways...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Ivan Corwin

27
27

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 27

######
favorite 0

######
comment 0

“It is not from the benevolence of the butcher, the brewer, or the baker,that we expect our dinner, but from their regard for their own interest.”Each participant in a competitive economy is “led by an invisible hand topromote an end which was no part of his intention.” Adam Smith, 1776.With his treatise, The Wealth of Nations, 1776, Adam Smith initiated the field of economics,and his famous quote provided this field with its central guiding principle. The pioneeringwork of Walras...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Vijay V Vazirani

42
42

Feb 20, 2014
02/14

by
Microsoft Research

movies

######
eye 42

######
favorite 0

######
comment 0

Understanding Gibbs measures on trees and their spatial mixing thresholds (uniqueness, strong spatial mixing, reconstruction) can give insight into the behavior of Gibbs measures on general graphs, in particular random graphs which are locally tree-like. We discuss two results: In the first result, we show that counter to the general notion that the d regular tree is the worst case for decay of correlation between sets and nodes among all d regular graphs, we produce an example of a spin...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Allan Sly

183
183

Oct 30, 2014
10/14

by
Microsoft Research

movies

######
eye 183

######
favorite 0

######
comment 0

In 1999 A. Barabasi and R. Albert suggested the idea of preferential attachment to explain the power law distribution of the vertex degrees in web graphs. Several mathematical models have then appeared incorporating this idea. Among them, the LCD model by B. Bollobas and O. Riordan, the Buckley--Osthus model, the Bollobas--Borgs-Chayes--Riordan model of directed scale-free graphs, etc. Many deep results have been obtained concerning these models. For example, one studies the degree...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Andrey Raigorodsky

32
32

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 32

######
favorite 0

######
comment 0

We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a random algorithm by keeping the accumulated rounding errors as small as possible.Our new algorithm surprisingly closely approximates the idealized process (where the tokens are divisible) on important network topologies. On d-dimensional torus graphs with n nodes it deviates from the idealized process only by an additive...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Tobias Friedrich

29
29

Sep 30, 2014
09/14

by
Microsoft Research

movies

######
eye 29

######
favorite 0

######
comment 0

Consider the standard Ising model on a finite n x n grid at low temperature. If the boundary spins are held fixed equal to +1 it is believed that the mixing time of the corresponding Glauber dynamics (Gibbs sampler) is poly(n). Although such a result is still far from being proved, recently there has been some exciting progress using the censoring inequality by Peres and P. Winkler together with inductive schemes. The final outcome is a quasi-poly(n) bound valid for all temperatures below the...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Fabio Martinelli

10
10.0

Sep 30, 2014
09/14

by
Microsoft Research

movies

######
eye 10

######
favorite 0

######
comment 0

We consider the stochastic evolution of a (1 + 1)-dimensional polymer in the depinned regime. At equilibrium the system exhibits a double well structure: the polymer lies(essentially) either above or below the repulsive line. As a consequence one expects a metastable behavior with rare jumps between the two phases combined with a fast thermalization inside each phase. However the energy barrier between these two phases is only logarithmic in the system size L and therefore the two relevant time...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Fabio Toninelli

14
14

Oct 6, 2014
10/14

by
Microsoft Research

movies

######
eye 14

######
favorite 0

######
comment 0

A number of data sets are naturally described in matrix form. Examples range from microarrays to collaborative filtering data, to the set of pairwise distances of a cloud of points. In many of these examples, singular value decomposition (SVD) provides an efficient way to construct a low-rank approximation thus achievieng both dimensionality reduction, and effective denoising. SVD is also an important tool in the design of approximate linear algebra algorithms for massive data sets. It is a...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Andrea Montanari

51
51

Feb 10, 2014
02/14

by
Microsoft Research

movies

######
eye 51

######
favorite 0

######
comment 0

We model situations in which a principal provides incentives to a groupof agents to participate in a project (such as a social event, commercialactivity or the adoption of a certain technological standartization).Agents' benefits from participation depend on the identity of otherparticipating agents. We assume bilateral externalities and characterize theoptimal incentive mechanism. Using a graph-theoretic approach we show thatthe optimal mechanism provides a ranking of incentives for the...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Eyal Winter

32
32

Apr 30, 2014
04/14

by
Microsoft Research

movies

######
eye 32

######
favorite 0

######
comment 0

Part 1: 'The Communication Complexity of Uncoupled Nash Equilibrium Procedures', by Sergiu Hart and Yishay Mansour http://www.ma.huji.ac.il/hart/abs/comcom.html We study the question of how long it takes players to reach a Nash equilibrium in 'uncoupled' setups, where each player initially knows only his own payoff function. We derive lower bounds on the number of bits that need to be transmitted in order to reach a Nash equilibrium, and thus also on the required number of steps. These lower...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Sergiu Hart

38
38

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 38

######
favorite 0

######
comment 0

Consider a random Galton-Watson tree conditioned to have size n.We assume that the offspring distribution has mean 1 and finite variance, but no further moment conditions.It is well-known that the width and height both are of the order n 1/2 (see for example Aldous (1991) for much more detailed results on the shape). I will talk about about proving tail estimates, for example P(width > k) < exp(-c k 2 /n). (Note that no such exponential tail bounds are assumed for the offspring...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Svante Janson

89
89

Apr 30, 2014
04/14

by
Microsoft Research

movies

######
eye 89

######
favorite 0

######
comment 0

Let C n be the n’th generation in the construction of the middle-half Cantor set. The Cartesian square K n of C n consists of 4 n squares of side-length 1/(4 n ). The chance that a long needle thrown at random in the unit square will meet K n is essentially the average length of the projections of K n . It is still an open problem to determine the exact rate of decay of this average. Until recently, the only explicit upper bound exp(- log_* n) was due to Peres and Solomyak. (log_* n is the...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Fedor Nazarov

29
29

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 29

######
favorite 0

######
comment 0

The cover time of a finite graph G (the expected time for simple random walk to visit all vertices) has been extensively studied, yet a number of fundamental questions concerning cover times have remained open: Aldous and Fill (1994) asked whether there is a deterministic polynomial-time algorithm that computes the cover time up to an O(1) factor; Winkler and Zuckerman (1996) defined the blanket time (when the empirical distribution of the walk is within a factor of 2, say, of the stationary...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Yuval Peres

32
32

Sep 29, 2014
09/14

by
Microsoft Research

movies

######
eye 32

######
favorite 0

######
comment 0

The notable KKL Theorem of Kahn, Kalai, and Linial says that if f : 0,1 n - 0,1 is a balanced boolean function, then there is at least one coordinate i with "influence" at least Omega(log n / n).We generalize this result to boolean functions on Cayley and Schreier graphs, whenever the generating set is a union of conjugacy classes and the associated Markov chain has a good log-Sobolev constant. E.g., we show that if f is a balanced Boolean function on the set of n-bit strings with...

Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Ryan O'Donnell